import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * 给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。
 * https://leetcode.cn/problems/hua-dong-chuang-kou-de-zui-da-zhi-lcof/
 */
class Intcmp implements Comparator<int[]> {

    @Override
    public int compare(int[] o1, int[] o2) {
        return o2[1]-o1[1];
    }
}

public class MaxSlidingWindow {
    public int[] maxSlidingWindow(int[] nums, int k) {
        Intcmp cmp=new Intcmp();
        PriorityQueue<int[]>maxHeap=new PriorityQueue<>(cmp);
        int len=nums.length;
        if(len==0){
            return new int[0];
        }
        int[] ret=new int[len-k+1];
        for(int i=0;i<k;i++){
            maxHeap.offer(new int[]{i,nums[i]});//存储下标和对应的值
        }
        int index=0;
        ret[index++]=maxHeap.peek()[1];
        for(int i=k;i<len;i++){
            while(!maxHeap.isEmpty()&&i-maxHeap.peek()[0]>=k){
                maxHeap.poll();
            }
            maxHeap.offer(new int[]{i,nums[i]});
            ret[index++]=maxHeap.peek()[1];
        }
        return ret;
    }
}